package com.zdp.algorithm.stackandqueue;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 使用两个栈来实现队列
 * @author Zhengdp
 * @date 2023年01月05日 10:57
 */
public class TwoStackQueue {
    private static int[] elements = new int[]{
            1,2,3,4,5,6,7,8
    };
    private static int[] elements2 = new int[] {
            11,12,13,14
    };
    public static void main(String[] args) {
      TowStackQueueImpl<Integer> queue = new TowStackQueueImpl<>();
      for(int element :elements) {
          queue.add(element);
      }
        System.out.println("出队列 ： " + queue.peek());
      queue.pop();
      for(int element : elements2) {
          queue.add(element);
      }
      while(!queue.isEmpty()) {
          System.out.print(queue.pop() + " , ");
      }
    }
}

/**
 * 使用栈来实现队列的功能
 * 队列 ：先进先出   栈 ： 先进后出
 * 可以使用两个栈来实现队列的功能。 stackPush 和 stackPop
 * 不难发现，将一个栈中的所有元素依次出栈，压入另一个栈中。
 * 然后另一个栈中出栈的元素顺序就与队列弹出的元素顺序相同。
 * （因此我们只需要在一个合适的时机，将stackPush栈中的所有元素弹出，压入到stackPop中即可）
 * 但是需要注意两点：
 * 1. 每次的弹出压入操作，必须是将stackPush栈中的所有元素压入到stackPop中（保证元素的顺序）
 * 2. 当stackPop中有元素时，不能执行弹出压入操作（不然会破坏stackPop中的元素顺序)
 * 目前的设计是在队列`pop()`或者`peek()`操作时，去尝试完成弹出压入操作。
 */
class TowStackQueueImpl<T> {
    private Stack<T> stackPush;
    private Stack<T> stackPop;

    public TowStackQueueImpl(){
        stackPop = new Stack<>();
        stackPush = new Stack<>();
    }

    public void add(T element) {
        stackPush.add(element);
    }

    /**
     * 将 stackPush中的所有元素弹出，压入到stackPop中
     */
    private void pushToPop(){
        if(!stackPush.isEmpty() && stackPop.isEmpty()) {
            while(!stackPush.isEmpty()) {
                stackPop.push(stackPush.pop());
            }
        }
    }

    public T pop(){
        if(stackPop.isEmpty() && stackPush.isEmpty()) {
            throw new RuntimeException("当前队列中无元素");
        }
        pushToPop();
        return stackPop.pop();
    }

    public T peek() {
        if(stackPop.isEmpty() && stackPush.isEmpty()) {
            throw new RuntimeException("当前队列中无元素");
        }
        pushToPop();
        return stackPop.peek();
    }

    public boolean isEmpty(){
        return stackPop.isEmpty() && stackPush.isEmpty();
    }
}
